package warm100;

import utils.TreeNode;

public class lowestCommonAncestor_236 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //后序遍历，记录子树中是否有对应节点
        find(root, p, q);
        return ans;
    }

    TreeNode ans = null;
    boolean isFind = false;  //已经找到

    /**
     * 返回节点中是否含有所需节点
     */
    public boolean find(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return false;
        boolean left = find(root.left, p, q);
        boolean right = find(root.right, p, q);
        if (!isFind) {            //还没找到祖先节点
            if (left && right) {   //左右子树中含有对应两个节点
                isFind = true;
                ans = root;
                return true;
            } else if (root == p || root == q) {//自身是要找节点，
                if (left || right) {
                    ans = root;   //左右子树中有一个要找节点自身就是祖先节点
                    isFind = true;
                }
                return true;//左右子树一个没有
            }else if(left || right)
                return true;//该子树中含有一个
            return false;//该子树中不含有
        }
        return true;  //无用返回
    }

    /**
     * 高级写法
     */
    public static TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            /**
             * 代码通过返回值来判定查找结果且只有三种可能：null/两个目标结点之一/公共祖先
             * 在这里找到一个目标结点直接返回
             * 1，如果另一个目标结点在更深处
             * 则说明当前结点即为最近公共祖先，直接返回没问题。
             * 2，如果另一个目标结点在另一棵子树上，
             * 也没必要继续查找，也应该直接返回。
             */
            return root;
        }
        TreeNode left = lowestCommonAncestor2(root.left, p, q);      //左子树返回的节点
        TreeNode right = lowestCommonAncestor2(root.right, p, q); //右子树返回的节点
        /**
         * 因为我们设定的条件是只能返回想要的节点或者null
         * 如果左右结点同时出现且不为空，则说明找到了公共祖先，返回当前节点即可。
         * 因为是采用后根遍历，可以保证找到的一定是最近公共祖先
         */
        if (left != null && right != null) {
            return root;
        }
        /**
         * 关键步骤
         * 在没有完全找到 p 或者 q 的情况下返回，在这种情况下可分为两种可能：
         * 1.只找到一个目标结点，则返回left和right中非null的一个
         * 2.一个都没有找到，则left = right = null，返回null
         */
        return left != null ? left : right;
    }
}
